package com.techyuan.algorithm.dp;

import com.techyuan.algorithm.utils.PrintUtil;
import org.apache.commons.lang.ArrayUtils;

import java.util.ArrayList;
import java.util.List;

/**
 * 状态方程
 * c[i,w] = 0;i=0
 * c[i,w] = c[i-1,w],pw[i]>w
 * c[i,w] = max{ c[i-1,w-pw[i]]+p[i],c[i-1,w]};i>0,pw[i]<w
 * Created by Administrator on 2017/2/24.
 */
public class OneZeroBag {
    /**
     * @param p  物品单价
     * @param pw 物品重量
     * @param W  背包可容重量
     * @return
     */
    private static int[] buildOZBag(int[] p, int[] pw, int W) {
        int[][] r = new int[p.length + 1][W + 1];
        int[][] c = new int[p.length + 1][W + 1];
        int minpw = Integer.MAX_VALUE;
        for (int tpw : pw) {
            if (tpw < minpw)
                minpw = tpw;
        }
        for (int i = 1; i <= p.length; i++) {
            for (int w = minpw; w <= W; w++) {
                if (pw[i - 1] > w)
                    c[i][w] = c[i - 1][w];
                else if (c[i - 1][w - pw[i - 1]] + p[i - 1] > c[i - 1][w]) {
                    c[i][w] = c[i - 1][w - pw[i - 1]] + p[i - 1];
                    r[i][w] = 1;
                } else {
                    c[i][w] = c[i - 1][w];
                    r[i][w] = 0;
                }
            }
        }

        int[] ret = new int[0];
        int tmpW = W;
        int i = p.length;
        while (tmpW > 0) {
            if (r[i][tmpW] == 1) {
                tmpW = tmpW - pw[i - 1];
                ret = ArrayUtils.add(ret, i - 1);
            } else {
                i = i - 1;
            }
        }

        return ret;
    }

    public static void main(String[] args) {
        int pw[] = {3, 4, 7, 8, 9};
        int p[] = {4, 5, 10, 11, 13};
        int W = 17;
        int[] bagObjArr = buildOZBag(p, pw, W);
        PrintUtil.printArrPretty(bagObjArr);
        int wBag = 0, pBag = 0;
        for (int i : bagObjArr) {
            wBag += pw[i];
            pBag += p[i];
        }
        System.out.println("包裹限制重量" + W + ",物品总重量:" + wBag);
        System.out.println("包裹总价值:" + pBag);
    }
}
